#include <iostream>
using namespace std;

#include "ProgCommon.h"
#include "MinHeap.h"


template<class T>
void ShowList( T a[], int from, int to )
{
    cout << "[ ";
    for ( int i = from; i <= to; i++ ) {
        cout << a[i] << " ";
    }
    cout << "]";
}

template<class T>
void HeapSortSimple( T a[], int n )
{
    MinHeap<T> H( 1 );
    H.Initialize( a, n, n );

    T x;
    for ( int i = n-1; i >= 1; i-- ) {
        H.DeleteMin( x );
        printf( " * delete min val : " );
        ConSetColor( FG_YELLOW );
        printf( "%d\n", x );
        ConSetColor( COLOR_DEFAULT );
        a[i+1] = x;
    }
    printf( " * delete min val : " );
    ConSetColor( FG_YELLOW );
    printf( "%d\n", a[1] );
    H.Deactivate();
}

int main()
{
    RAND_SEED;
    PROG_BANNER;

    int n = RandomInt( 7, 12 );
    int *a = new int[n+1];

    for ( int i = 1; i <= n; i++ ) {
        a[i] = RandomInt( 1, 10 );
    }

    ConSetColor( FG_CYAN );
    printf( "Prog 7: MinHeap Sort\n" );
    ConSetColor( COLOR_DEFAULT );

    printf( "Random array is: " );
    ConSetColor( FG_GREEN );
    ShowList( a, 1, n );
    ConSetColor( COLOR_DEFAULT );
    printf( "\n" );

    HeapSortSimple( a, n );

    printf( "Sorted array is: " );
    ConSetColor( FG_RED );
    ShowList( a, 1, n );
    ConSetColor( COLOR_DEFAULT );

    printf( "\n" );
    PROG_BANNER;
    PROG_PAUSE;
    return 0;
}

